/*
 * @(#)ConvertGraphToTree.java
 *
 * Revision:
 * Author                                         Date           
 * --------------------------------------------   ------------   
 *  Jeremias D. Serafim de Araujo                     14/11/2012    
 */

package br.edu.ufcg.splab.generator;

import java.util.ArrayList;
import java.util.UUID;

import br.edu.ufcg.splab.core.InterfaceEdge;
import br.edu.ufcg.splab.core.InterfaceGraph;
import br.edu.ufcg.splab.core.InterfaceVertex;
import br.edu.ufcg.splab.core.graph.Tree;
import br.edu.ufcg.splab.core.vertex.Node;


/**
 *	This class generates a tree from a graph. 
 *	This tree is a graph without loops
 *
 * Converting a graph to a tree, we detect the presence of loop 
 * when the vertex of the graph is visited for the second time, 
 * we generate subtrees that represent the loop, from the vertex
 * marked, and with the subtrees doing n expansions
 * 
 **/

public class ConvertGraphToTree {

	/**
	 * The tree generated
	 * */
	private Tree t;

	/**
	 * Constructor
	 * */
	public ConvertGraphToTree() {

	}

	/**
	 *  The method receives a graph and converts it to a tree
	 *  
	 * @param graph is the model that will converted  into tree
	 * @return Tree tree 
	 */
	public Tree converterGraph(InterfaceGraph graph){

		t = new Tree();
		
		ArrayList< InterfaceVertex> vertexVisiteds = new ArrayList< InterfaceVertex>();
		dfsGenerateTree(graph.getRoot(),null, vertexVisiteds);
		vertexVisiteds.clear();
		//quando criar a tree ela vai criar suas subTrees
		
		t.generateSubTrees();
		return this.t;
	}

	//aqui nois exercemos os vertices do grafo e de acordo com os mesmos, comecamos a montar a nossa tree
	//eliminando os loops presentes no modelo
	
	/**
	 * 
	 * We walk in the graph and exercising their edges 
	 * create a tree, for this we used a traditional dfs.
	 * 
	 * 
	 * @param vertex is the vertex root of graph
	 * @param uuidFrom is the uuid of vertexFrom
	 * @param vertexVisites is a collection of vertex that visited in the moment
	 */
	
	private void dfsGenerateTree(InterfaceVertex vertex,UUID uuidFrom,ArrayList<InterfaceVertex> vertexVisiteds) {
		
		if (uuidFrom == null) {
			uuidFrom = t.addNode(vertex.getLabel());
		}
		for (InterfaceEdge edge : vertex.getOutTransitions()) {		
			if (!vertexVisiteds.contains(vertex)) {
				vertexVisiteds.add(vertex);
				InterfaceVertex vertexTo = edge.getTo();		
				UUID uuidvTo = t.addNode(vertexTo.getLabel());
				InterfaceEdge newEdge = t.addEdge(uuidFrom,edge.getLabel(),uuidvTo);
				newEdge.setType(edge.getType());

				dfsGenerateTree(vertexTo, uuidvTo,vertexVisiteds);
				vertexVisiteds.remove(vertex);
				
			} else if (vertexVisiteds.contains(vertex)) {
				Node n =(Node) t.getStates().get(uuidFrom);
				n.setKeyMarked(n.getUUID().toString());
				t.addNodeMarked(uuidFrom,n);
			}
		}
	}
	

}

